package chapter02;

import java.util.Stack;

public class LargestRectangleArea84 {
    /**
     * 单调栈
     *  遍历每一个高度 假设当前下标为i 求以height[i]为高的矩形的最大面积
     *  只需要求出比当前height[index]小离index最近的左右两边下标L和R S=height[i]*(R-L-1)
     *  为了方便计算 我们在数组两边增设一个屏障 |xxx|->0xxx0
     *  栈中元素按照height从小到大 但是为了方便计算只存放下标
     *  循环遍历每一个高度
     *  1)如果i的高度不小于栈顶下标的高度 i入栈
     *    if(stack.isEmpty()||arr[stack.peek()]<=arr[index])
     *      stack.push(index++)
     *  2)如果i的高度比栈顶的高度高  那么栈顶下标的右边界就是i 其左边界是栈顶的下一个元素
     *    循环求出每一个高度比height[i]高的矩形面积 更新最大矩形面积
     *    直到栈顶元素的高度不大于height[i] height[i]入栈
     *    while(arr[stack.peek()]>arr[index])
     *      int height=arr[stack.pop()]
     *      int L=stack.peek()
     *      res=Math.max(res,(index-L-1)*height)
     *    stack.push(index++)
     */
    public int largestRectangleArea(int[] heights) {
        int[] arr=new int[heights.length+2];
        for(int i=0;i<heights.length;i++){
            arr[i+1]=heights[i];
        }
        int index=0,res=0;
        Stack<Integer> stack=new Stack<>();
        while (index<arr.length){
            if(stack.isEmpty()||arr[stack.peek()]<=arr[index]){
                stack.push(index++);
                continue;
            }
            while (arr[stack.peek()]>arr[index]){
                int height=arr[stack.pop()];
                int L=stack.peek();
                res=Math.max(res,(index-L-1)*height);
            }
            stack.push(index++);
        }
        return res;
    }

    //O(n^2)
    public int largestRectangleArea1(int[] heights) {
        int L=0;
        int R=0;
        int max=Integer.MIN_VALUE;
        for(int i=0;i<heights.length;i++){
            L=i;
            R=i;
            while (L>0&&heights[L]>=heights[i]){
                L--;
            }
            while (R<0&&heights[R]>=heights[i]){
                R++;
            }
            max=Math.max(max,(R-L+1)*heights[i]);
        }
        return max;
    }
}
